package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 86. 分隔链表
 * @date 2025/5/18 12:43
 */
public class E86 {

    /**
     * 思路：分别拼接两部分链表，最后合并
     *
     * @param head 头节点
     * @param x    值
     * @return 新链表
     */
    public ListNode partition(ListNode head, int x) {
        ListNode smallSentinel = new ListNode(), currSmall = smallSentinel;
        ListNode largeSentinel = new ListNode(), currLarge = largeSentinel;
        while (head != null) {
            if (head.val < x) {
                currSmall.next = new ListNode(head.val);
                currSmall = currSmall.next;
            } else {
                currLarge.next = new ListNode(head.val);
                currLarge = currLarge.next;
            }
            head = head.next;
        }
        currSmall.next = largeSentinel.next;
        return smallSentinel.next;
    }
}
